/*
  给你一个字符串 s ，请你反转字符串中 单词 的顺序。
  单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
  返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
  注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。
  返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
*/
// 方法一：使用js中的一些方法实现，剔除多个空格可以用filter
var reverseWords = function (s) {
  let arr = s.split(' ').filter(item => item !== '')
  return arr.reverse().join(' ')
}


// 方法二：使用字符串处理
var reverseWords2 = function (s) {
  // 字符串转数组
  const strArr = Array.from(s)
  // 移除多余空格
  removeExtraSpaces(strArr)
  // 翻转
  reverse(strArr, 0, strArr.length - 1)
  let start = 0
  for (let i = 0; i <= strArr.length; i++) {
    if (strArr[i] === ' ' || i === strArr.length) {
      // 翻转单词
      reverse(strArr, start, i - 1)
      start = i + 1
    }
  }
  return strArr.join('')
}
// 删除多余空格
function removeExtraSpaces (strArr) {
  let slowIndex = 0
  let fastIndex = 0
  while (fastIndex < strArr.length) {
    // 移除开始位置和重复的空格
    if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {
      fastIndex++
    } else {
      strArr[slowIndex++] = strArr[fastIndex++]
    }
  }
  // 移除末尾空格
  strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex
}
// 翻转从 start 到 end 的字符
function reverse (strArr, start, end) {
  let left = start
  let right = end

  while (left < right) {
    // 交换
    [strArr[left], strArr[right]] = [strArr[right], strArr[left]]
    left++
    right--
  }
}